namespace Matrix
{
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, MAX_W, Direction> Self;
	public:
		Graph(const V* vertexs, int n)
		{
			_vertexs.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertexs.push_back(vertexs[i]);
				_IndexMap[vertexs[i]] = i;
			}

			_matrix.resize(n);
			for (int i = 0; i < n; i++)
				_matrix[i].resize(n, MAX_W);
		}

		W Kruskal(Self& minTree)
		{
			size_t n = _vertexs.size();

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, MAX_W);
			}

			priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (i < j && _matrix[i][j] != MAX_W)
					{
						minque.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}

			// 选出n-1条边
			int size = 0;
			W totalW = W();
			UnionFindSet ufs(n);
			while (!minque.empty())
			{
				Edge min = minque.top();
				minque.pop();

				if (!ufs.InSet(min._srci, min._dsti))
				{
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
					minTree._AddEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					++size;
					totalW += min._w;
				}
				else
				{
					cout << "构成环：";
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":" << min._w << endl;
				}
			}

			if (size == n - 1)
			{
				return totalW;
			}
			else
			{
				return W();
			}
		}

		void _AddEdge(size_t srci, size_t dsti, const W& w)
		{
			_matrix[srci][dsti] = w;
			if (Direction == false)
				_matrix[dsti][srci] = w;
		}
		void AddEdge(const V& src, const V& dst, const W& w)
		{ 
			size_t srci = GetVertexsIndex(src);
			size_t dsti = GetVertexsIndex(dst);

			_AddEdge(srci, dsti, w);
		}

		size_t GetVertexsIndex(int src)
		{
			auto ret = _IndexMap.find(src);
			if (ret != _IndexMap.end())
				return ret->second;
			else
			{
				throw invalid_argument("不存在的顶点");
				return -1;
			}
		}

		void BFS(const V& src)
		{
			size_t srci = GetVertexsIndex(src);
			queue<size_t> q;
			q.push(srci);
			size_t len = 1;
			vector<bool> visited(_vertexs.size(), false);
			visited[srci] = true;

			while (!q.empty())
			{
				for (int i = 0; i < len; i++)
				{
					size_t front = q.front();
					q.pop();
					cout << front << ':' << _vertexs[front] << ' ';
					
					for (size_t j = 0; j < _vertexs.size(); j++)
					{
						if (_matrix[front][j] != MAX_W && visited[j] == false)
						{
							q.push(j);
							visited[j] = true;
						}
					}
				}
				cout << endl;
				len = q.size();
			}
		}

		void _DFS(size_t srci, vector<bool>& visited)
		{
			cout << srci << ':' << _vertexs[srci] << endl;
			visited[srci] = true;

			for (size_t i = 0; i < _vertexs.size(); i++)
				if (_matrix[srci][i] != MAX_W && visited[i] == false)
					_DFS(i, visited);
		}
		void DFS(const V& src)
		{
			size_t srci = GetVertexsIndex(src);
			vector<bool> visited(_vertexs.size(), false);
			_DFS(srci, visited);
		}

		size_t GetVertexsIndex(const V& src)
		{
			auto ret = _IndexMap.find(src);
			if (ret != _IndexMap.end())
				return ret->second;
			else
			{
				throw invalid_argument("不存在的顶点");
				return -1;
			}
		}

		void Print()
		{
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				for (size_t j = 0; j < _matrix[i].size(); j++)
					if (_matrix[i][j] == MAX_W)
						cout << "* ";
					else
						cout << _matrix[i][j] << ' ';

				cout << endl;
			}
		}

	private:
		map<V, int> _IndexMap;     // 顶点下标
		vector<V> _vertexs;        // 顶点集合
		vector<vector<W>> _matrix; // 矩阵
	};

	void test1()
	{
		string a[] = { "张三", "李四", "王五", "赵六", "周七" };
		Graph<string, int> g1(a, 5);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.AddEdge("王五", "周七", 30);
		g1.Print();

		cout << endl;

		g1.BFS("张三");
		cout << endl;
		g1.DFS("张三");
	}
}

namespace Adjacency_tables
{
	template<class W>
	struct Edge
	{
		W _w;
		Edge<W>* _next;
		size_t _dsti;

		Edge(size_t dsti, const W& w)
			:_w(w)
			,_dsti(dsti)
			,_next(nullptr)
		{}
	};

	template<class V, class W, bool Direction = false>
	class Graph
	{
		typedef Edge<W> Edge;
	public:
		Graph(const V* vertexs, int n)
		{
			_vertexs.reserve(n);
			for (int i = 0; i < n; i++)
			{
				_vertexs.push_back(vertexs[i]);
				_indexMap[vertexs[i]] = i;
			}

			_tables.resize(n, nullptr);
		}

		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexsIndex(src);
			size_t dsti = GetVertexsIndex(dst);
			
			Edge* eg = new Edge(dsti, w);
			eg->_next = _tables[srci];
			_tables[srci] = eg;

			if (Direction == false)
			{
				Edge* egd = new Edge(srci, w);
				egd->_next = _tables[dsti];
				_tables[dsti] = eg;
			}
		}

		size_t GetVertexsIndex(const V& src)
		{
			auto ret = _indexMap.find(src);
			if (ret != _indexMap.end())
				return ret->second;
			else
			{
				throw invalid_argument("不存在的顶点");
				return -1;
			}
		}

		void Print()
		{
			// 顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cout << _vertexs[i] << "[" << i << "]->";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
					cur = cur->_next;
				}
				cout << "nullptr" << endl;
			}
		}

	private:
		map<V, int> _indexMap;   // 顶点映射下标
		vector<V> _vertexs;      // 顶点集合
		vector<Edge*> _tables;   // 邻接表
	};

	void test1()
	{
		string a[] = { "张三", "李四", "王五", "赵六" };
		Graph<string, int> g1(a, 4);
		g1.AddEdge("张三", "李四", 100);
		g1.AddEdge("张三", "王五", 200);
		g1.AddEdge("王五", "赵六", 30);
		g1.Print();
	}
}

//namespace Matrix
//{
//	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
//	class Graph
//	{
//	public:
//		Graph(const V* v, size_t n)
//		{
//			_vertexs.reserve(n);
//			for (size_t i = 0; i < n; i++)
//			{
//				_vertexs.push_back(v[i]);
//				_vIndexMap[v[i]] = i;
//			}
//
//			_matrix.resize(n);
//			for (size_t i = 0; i < _matrix.size(); i++)
//				_matrix[i].resize(n, MAX_W);
//		}
//
//		void _AddEdge(const V& src, const V& dst, const W& w)
//		{
//			size_t srci = GetVertexIndex(src);
//			size_t dsti = GetVertexIndex(dst);
//			AddEdge(srci, dsti, w);
//		}
//		void AddEdge(size_t srci, size_t dsti, const W& w)
//		{
//			_matrix[srci][dsti] = w;
//			if (Direction == false)
//				_matrix[dsti][srci] = w;
//		}
//
//		void BFS(const V& src)
//		{
//			size_t srci = GetVertexIndex(src);
//
//			queue<size_t> q;
//			q.push(srci);
//
//			vector<bool> visited(_vertexs.size(), false);
//			visited[srci] = true;
//
//			size_t levelLen = 1;
//			while (!q.empty())
//			{
//				for (size_t i = 0; i < levelLen; i++)
//				{
//					size_t front = q.front();
//					q.pop();
//					cout << front << ':' << _vertexs[front] << ' ';
//
//					for (size_t j = 0; j < _vertexs.size(); j++)
//					{
//						if (_matrix[front][j] != MAX_W && visited[j] == false)
//						{
//							q.push(j);
//							visited[j] = true;
//						}
//					}
//				}
//				cout << endl;
//				levelLen = q.size();
//			}
//		}
//
//		void _DFS(size_t srci, vector<bool>& visited)
//		{
//			cout << srci << ':' << _vertexs[srci] << endl;
//			visited[srci] = true;
//
//			for (size_t i = 0; i < _vertexs.size(); i++)
//				if (_matrix[srci][i] != MAX_W && visited[i] == false)
//					_DFS(i, visited);
//		}
//		void DFS(const V& src)
//		{
//			size_t srci = GetVertexIndex(src);
//			vector<bool> visited(_vertexs.size(), false);
//			_DFS(srci, visited);
//		}
//
//		size_t GetVertexIndex(const V& v)
//		{
//			auto ret = _vIndexMap.find(v);
//			if (ret != _vIndexMap.end())
//				return ret->second;
//			else
//			{
//				throw invalid_argument("不存在的顶点");
//				return -1;
//			}
//		}
//
//		void Print()
//		{
//			for (size_t i = 0; i < _matrix.size(); i++)
//			{
//				for (size_t j = 0; j < _matrix[i].size(); j++)
//					if (_matrix[i][j] == MAX_W)
//						cout << "* ";
//					else
//						cout << _matrix[i][j] << ' ';
//				cout << endl;
//			}
//		}
//
//	private:
//		map<V, size_t> _vIndexMap; 
//		vector<V> _vertexs;         // 顶点集合
//		vector<vector<W>> _matrix;  // 储存边的集合的矩阵
//	};
//
//	void test1()
//	{
//		string a[] = { "张三", "李四", "王五", "赵六", "周七" };
//		Graph<string, int> g1(a, 5);
//		g1._AddEdge("张三", "李四", 100);
//		g1._AddEdge("张三", "王五", 200);
//		g1._AddEdge("王五", "赵六", 30);
//		g1._AddEdge("王五", "周七", 30);
//		g1.Print();
//
//		cout << endl;
//
//		g1.BFS("张三");
//		cout << endl;
//		g1.DFS("张三");
//	}
//
//	void TestGraph()
//	{
//		size_t v[] = {0,1,2,3,4,5,6,7,8};
//		Graph<size_t, int, INT_MAX> g(v, 9);
//
//		g._AddEdge(0, 1, 9);
//		g._AddEdge(2, 8, 9);
//		g._AddEdge(3, 6, 9);
//		g._AddEdge(4, 5, 9);
//		g._AddEdge(2, 7, 9);
//		g._AddEdge(2, 6, 9);
//		g._AddEdge(4, 6, 9);
//		g._AddEdge(5, 7, 9);
//
//		g.Print();
//
//		g._AddEdge(g.GetVertexIndex(1), g.GetVertexIndex(7), 6);
//		cout << endl;
//
//		g.Print();
//	}
//}

//namespace Adjacency_tables
//{
//	template<class W>
//	struct Edge
//	{
//		W _w;
//		size_t _dsti;
//		Edge<W>* _next;
//
//		Edge(size_t dsti, const W& w)
//			:_dsti(dsti)
//			,_w(w)
//			,_next(nullptr)
//		{}
//	};
//
//	template<class V, class W, bool Direction = false>
//	class Graph
//	{
//		typedef Edge<W> Edge;
//	public:
//		Graph(const V* v, size_t n)
//		{
//			_vertexs.reserve(n);
//			for (size_t i = 0; i < n; i++)
//			{
//				_vertexs.push_back(v[i]);
//				_indexMap[v[i]] = i;
//			}
//
//			_tables.resize(n, nullptr);
//		}
//
//		void AddEdge(const V& src, const V& dst, const W& w)
//		{
//			size_t srci = GetVertexIndex(src);
//			size_t dsti = GetVertexIndex(dst);
//
//			Edge* eg = new Edge(dsti, w);
//			eg->_next = _tables[srci];
//			_tables[srci] = eg;
//
//			if (Direction == false)
//			{
//				Edge* egd = new Edge(srci, w);
//				egd->_next = _tables[dsti];
//				_tables[dsti] = egd;
//			}
//		}
//
//		size_t GetVertexIndex(const V& v)
//		{
//			auto ret = _indexMap.find(v);
//			if (ret != _indexMap.end())
//				return ret->second;
//			else
//			{
//				throw invalid_argument("不存在的顶点");
//				return -1;
//			}
//		}
//
//		void Print()
//		{
//			// 顶点
//			for (size_t i = 0; i < _vertexs.size(); ++i)
//			{
//				cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
//			}
//			cout << endl;
//
//			for (size_t i = 0; i < _tables.size(); ++i)
//			{
//				cout << _vertexs[i] << "[" << i << "]->";
//				Edge* cur = _tables[i];
//				while (cur)
//				{
//					cout << "[" << _vertexs[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
//					cur = cur->_next;
//				}
//				cout << "nullptr" << endl;
//			}
//		}
//
//	private:
//		map<V, size_t> _indexMap;		// 顶点映射下标
//		vector<V> _vertexs;         // 顶点集合
//		vector<Edge*> _tables;		// 邻接表
//	};
//
//	void TestGraph1()
//	{
//		/*Graph<char, int, true> g("0123", 4);
//		g.AddEdge('0', '1', 1);
//		g.AddEdge('0', '3', 4);
//		g.AddEdge('1', '3', 2);
//		g.AddEdge('1', '2', 9);
//		g.AddEdge('2', '3', 8);
//		g.AddEdge('2', '1', 5);
//		g.AddEdge('2', '0', 3);
//		g.AddEdge('3', '2', 6);
//
//		g.Print();*/
//
//		string a[] = { "张三", "李四", "王五", "赵六" };
//		Graph<string, int> g1(a, 4);
//		g1.AddEdge("张三", "李四", 100);
//		g1.AddEdge("张三", "王五", 200);
//		g1.AddEdge("王五", "赵六", 30);
//		g1.Print();
//	}

	//void TestGraph()
	//{
	//	size_t v[] = { 0,1,2,3,4,5,6,7,8 };
	//	Graph<size_t, int, INT_MAX> g(v, 9);

	//	g._AddEdge(0, 1, 9);
	//	g._AddEdge(2, 8, 9);
	//	g._AddEdge(3, 6, 9);
	//	g._AddEdge(4, 5, 9);
	//	g._AddEdge(2, 7, 9);
	//	g._AddEdge(2, 6, 9);
	//	g._AddEdge(4, 6, 9);
	//	g._AddEdge(5, 7, 9);

	//	g.Print();

	//	g._AddEdge(g.GetVertexIndex(1), g.GetVertexIndex(7), 6);
	//	cout << endl;

	//	g.Print();
	//}
//}

//namespace Matrix
//{
//	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
//	class Graph
//	{
//	public:
//		Graph(const vector<V>& vertexs, size_t n)
//		{
//			_vertexs.reserve(n);
//			for (size_t i = 0; i < vertexs.size(); i++)
//			{
//				_vertexs.push_back(vertexs[i]);
//				_vIndexMap[_vertexs[i]] = i;
//			}
//
//			_matrix.resize(n);
//			for (auto& e : _matrix)
//			{
//				e.resize(n, MAX_W);
//			}
//		}
//
//		void _AddEdge(const V& srci, const V& dsti, const W& w)
//		{
//			_matrix[srci][dsti] = w;
//			if (!Direction)
//				_matrix[dsti][srci] = w;
//		}
//
//		size_t GetVertexIndex(const V& v)
//		{
//			auto ret = _vIndexMap.find(v);
//			if (ret != _vIndexMap.end())
//			{
//				return ret->second;
//			}
//			else
//			{
//				throw invalid_argument("不存在的顶点");
//				return -1;
//			}
//		}
//
//		void Print()
//		{
//			for (size_t i = 0; i < _matrix.size(); i++)
//			{
//				for (size_t j = 0; j < _matrix[i].size(); j++)
//				{
//					if (_matrix[i][j] == MAX_W)
//						cout << "* ";
//					else
//						cout << _matrix[i][j] << ' ';
//				}
//				cout << endl;
//			}
//		}
//
//	private:
//		map<V, size_t> _vIndexMap; 
//		vector<V> _vertexs;         // 顶点集合
//		vector<vector<W>> _matrix;  // 储存边的集合的矩阵
//	};
//
//	void TestGraph()
//	{
//		vector<int> v = { 0,1,2,3,4,5,6,7,8 };
//		Graph<int, int, INT_MAX> g(v, 9);
//
//		g._AddEdge(0, 1, 9);
//		g._AddEdge(2, 8, 9);
//		g._AddEdge(3, 6, 9);
//		g._AddEdge(4, 5, 9);
//		g._AddEdge(2, 7, 9);
//		g._AddEdge(2, 6, 9);
//		g._AddEdge(4, 6, 9);
//		g._AddEdge(5, 7, 9);
//
//		g.Print();
//
//		g._AddEdge(g.GetVertexIndex(1), g.GetVertexIndex(7), 6);
//		cout << endl;
//
//		g.Print();
//	}
//
//	//void TestGraph()
//	//{
//	//	Graph<char, int, INT_MAX, true> g("0123", 4);
//	//	g.AddEdge('0', '1', 1);
//	//	g.AddEdge('0', '3', 4);
//	//	g.AddEdge('1', '3', 2);
//	//	g.AddEdge('1', '2', 9);
//	//	g.AddEdge('2', '3', 8);
//	//	g.AddEdge('2', '1', 5);
//	//	g.AddEdge('2', '0', 3);
//	//	g.AddEdge('3', '2', 6);
//
//	//	g.Print();
//	//}
//}
